package com.linwen.excise.sort;

/**
 * shell排序是插入排序的改进版
 * 在间隔大的时候移动次数少
 * 在间隔少的时候移动距离段
 * @author : linwen
 * @date : 下午11:35 2021/6/1
 */
public class _04ShellSort {
    public static int[] shellSort(int[] arr){
        int temp=0;
        int count=0;
        int k = 1;
        while(k <= arr.length/3){
            //Kunth序列
            k = 3*k+1;
        }

        for (int h = k; h>0; h=(h-1)/3) {
            for (int i = h; i < arr.length; i++) {
                for (int j = i;j-h >= 0;j=j-h){
                    if(arr[j]<arr[j-h]){
                        count++;
                        temp = arr[j];
                        arr[j] = arr[j-h];
                        arr[j-h] = temp;
                    }
                }
            }
        }

        System.out.println(count);
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{9,6,11,3,5,12,8,7,10,15,14,4,1,13,2};
        //int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        shellSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"   ");
        }
    }
}
